import java.util.ArrayList;
import java.util.List;
public class TestBinaryTree {
    static  class TreeNode {
        public char val;
        public TreeNode Left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode root; // 代表二叉树的根节点

    public  TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.Left = B;
        A.right = C;
        B.Left = D;
        B.right = E;
        C.Left = F;
        C.right = G;
        E.right = H;
        this.root = A;
        return root;
    }

    //前序遍历 根左右
    public void perOrder(TreeNode root){
        // 可以是递归的 也可以是非递归的
        // 但80%都是递归的
        //递归打印

        //终止条件是
        if(root == null){
            return;
        }
        System.out.print(root.val+" ");
        perOrder(root.Left); // 开始递归左树
        perOrder(root.right);// 再开始递归右树
    }

    //获取二叉树中节点的个数
    //时间复杂度是：O（N）
    // 空间复杂度是： O(logN) //再最好情况下（满二叉树的情况下）
   public int size(TreeNode root){
        // 子问题： 左数的节点加右树的节点再加上一个1
       if(root == null){
           return 0;
       }
       int leftSize = size(root.Left);
       int rightSize = size(root.right);
       return leftSize+rightSize+1;
    }

    public static int nodeSize;//是一个成员变量
    public void size2(TreeNode root){
        // 遍历思路： 遇到节点就加一
        if(root==null){
            return ;
        }
        nodeSize++;
        size2(root.Left);
        size2(root.right);
    }

    //获取叶子节点的个数
    public int getLeafNodeCount(TreeNode root){
        // 一个节点的左树为空并且右树为空
        // 子问题思路：左叶子+右叶子
        if(root == null){
            return 0;
        }
        if(root.Left == null && root.right == null){
            return 1;
        }
        int leftLeaf = getLeafNodeCount(root.Left);
        int rightLeaf = getLeafNodeCount(root.right);
        return leftLeaf+rightLeaf;
    }

    public int leafSize;
    public void getLeafNodeCount1(TreeNode root) {
        if(root == null){
            return;
        }
        if(root.Left == null && root.right == null){
            leafSize++;
        }
        getLeafNodeCount1(root.Left);
        getLeafNodeCount1(root.right);
    }

    //获取第k层节点的个数
    int getKLeveNodeCount(TreeNode root,int k){
       // 子问题思路
        // 求第k层就是求每棵左右子树的第k-1层
        // （将其看成两棵树，就是求左子树的第k-1层+右子树的第k-1层）
        // 再继续下分，等变成第一层的时候开始求值
        if(root==null){
            return 0;
        }
        if ( k==1){
            return 1;
        }
       int leftSize =  getKLeveNodeCount(root.Left,k-1);
       int rightSize =  getKLeveNodeCount(root.right,k-1);
       return leftSize+rightSize;
    }

    //获取二叉树的高度
    public int getHeight(TreeNode root){
        // 子问题思路
        // 左子树的高度和右子树的高度求最大值再加1
        if (root == null){
            return 0;
        }
        int leftHeight = getHeight(root.Left);
        int rightHeight = getHeight(root.right);
        // 求最大值
        return (leftHeight > rightHeight) ? (leftHeight+1) : (rightHeight + 1);
    }
}
